package 岛屿问题;

import java.util.*;

/**
 * @author: AirMan
 * @date: 2025/6/3 21:16
 * @description:
 * 题目描述
 * 给定一个由 1（陆地）和 0（水）组成的矩阵，岛屿是被水包围，并且通过水平方向或垂直方向上相邻的陆地连接而成的。
 * 你可以假设矩阵外均被水包围。在矩阵中恰好拥有一个岛屿，假设组成岛屿的陆地边长都为 1，请计算岛屿的周长。岛屿内部没有水域。
 * 输入描述
 * 第一行包含两个整数 N, M，表示矩阵的行数和列数。之后 N 行，每行包含 M 个数字，数字为 1 或者 0，表示岛屿的单元格。
 * 输出描述
 * 输出一个整数，表示岛屿的周长
 */
public class Solution8 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int m = sc.nextInt();

        int[][] graph = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                graph[i][j] = sc.nextInt();
            }
        }

        int[][] dir = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};//下右上左逆时针遍历
        int result = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                // bfs
                if (graph[i][j] == 1) {
                    // bfs 采用队列形式，将当前节点的四周陆地加入到队列中
                    Deque<int[]> queue = new LinkedList();
                    int[] coordinate = new int[]{i, j};
                    queue.push(coordinate);
                    graph[i][j] = 2;
                    while (!queue.isEmpty()) {
                        coordinate = queue.pop();
                        int x = coordinate[0]; // 当前节点的横坐标
                        int y = coordinate[1]; // 当前节点的纵坐标
                        // 判断该陆地上下左右有几块接壤的水域，拥有几块水域，就说明有条边
                        // 并将四周的陆地加入到队列中
                        for (int k = 0; k < 4; k++) {
                            int nextX = x + dir[k][0];
                            int nextY = y + dir[k][1];
                            if (nextX < 0 || nextX >= graph.length || nextY < 0 || nextY >= graph[0].length) {
                                result++;
                                continue; //去除越界部分
                            }
                            if (graph[nextX][nextY] == 1) {
                                queue.add(new int[]{nextX, nextY});
                                graph[nextX][nextY] = 2;
                            } else if (graph[nextX][nextY] == 0){
                                result++;
                            }
                        }
                    }
                }
            }
        }

        System.out.println(result);
    }
}
